计算等比数列和时,需要递归计算。
#include <cstdio>
const int MAXN = 1.5e6; int Mod;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { if( x < 0 ) x += Mod; if( y < 0 ) y += Mod; return 1ll * x * y % Mod; }
int Squ( int x ) { return Mul( x , x ); }
int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = Squ( x ) ) if( po & 1 ) p = Mul( p , x ); return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return Mul( x , Inv( y ) ); }
int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve() {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) prime[ ++ prnum ] = i , mu[ i ] = -1;
for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
}
int Sum( int a1 , int q , int n ) { //首项为a1,公比为q,项数为n
if( n == 1 ) return a1;
int haf = Sum( a1 , q , n / 2 ) , amid = Quick_pow( q , n / 2 );
return Add( Mul( haf , amid + 1 ) , n & 1 ? Quick_pow( q , n ) : 0 );
}
int Solve( int n ) {
int Ans = 0;
for( int d = 1 ; d <= n ; d ++ ) {
int q1 = Quick_pow( d , d );
for( int j = 1 , q = q1 ; j <= n / d ; j ++ , q = Mul( q , q1 ) ) {
if( d == 1 )
Ans = Add( Ans , Mul( mu[ j ] , Squ( n / d / j ) ) );
else
Ans = Add( Ans , Mul( mu[ j ] , Squ( Sum( q , q , n / d / j ) ) ) );
}
}
return ( Ans + Mod ) % Mod;
}
int T , n;
signed main( ) {
sieve();
scanf("%d",&T);
while( T -- ) {
scanf("%d %d",&n,&Mod);
printf("%d\n", Solve( n ) );
}
return 0;
}
顺带一提,似乎式子可以继续化简,但不好计算。